#pragma once

template <class K>
struct BSTreeNode
{
    typedef BSTreeNode<K> Node;

    Node* _left;
    Node* _right;
    K _key;

    BSTreeNode(const K& key)
    :_left(nullptr),_right(nullptr),_key(key){}
};

template <class K>
class BSTree
{
    typedef BSTreeNode<K> Node;
public:
    bool insertR(const K& key)
    {
        return _insertR(_root,key);
    }

    bool findR(const K& key)
    {
        return _findR(_root,key);
    }

    bool eraseR(const K& key)
    {
        return _eraseR(_root,key);
    }

    void inorder()//中序遍历
    {
        _inorder(_root);
        cout << endl;
    }

private:
    bool _insertR(Node*& root,const K& key);
    bool _findR(Node* root,const K& key);
    bool _eraseR(Node*& root,const K& key);
    void _inorder(Node* root);
    
private:
    Node* _root = nullptr;
};

template <class K>
bool BSTree<K>::_insertR(Node*& root,const K& key)
{   
    if(root == nullptr)
    {
        root = new Node(key);
        return true;
    }

    if(root->_key > key)
    {
        return _insertR(root->_left,key);
    }
    else if(root->_key < key)
    {
        return _insertR(root->_right,key);
    }
    else
        return false;   
}

template <class K>
bool BSTree<K>::_findR(Node* root,const K& key)
{
    if(root == nullptr)
    {
        return false;
    }

    if(root->_key > key)
    {
        return _findR(root->_left,key);
    }
    else if(root->_key < key)
    {
        return _findR(root->_right,key);
    }
    else
        return true;   
}

template <class K>
bool BSTree<K>::_eraseR(Node*& root,const K& key)
{
    if(root == nullptr)
    {
        return false;
    }

    if(root->_key > key)
    {
        return _eraseR(root->_left,key);
    }
    else if(root->_key < key)
    {
        return _eraseR(root->_right,key);
    }
    else
    {
        Node* del = root;
        if(root->_left == nullptr)
        {
            root = root->_right;
        }
        else if(root->_right == nullptr)
        {
            root = root->_left;
        }
        else//左右都不为空
        {
            Node* left = root->_right;
            while(left->_left)
            {
                left = left->_left;
            }
            swap(left->_key,root->_key);
            return _eraseR(root->_right,key);
        }
        delete del;
        return true;
    }
}

template <class K>
void BSTree<K>::_inorder(Node* root)
{
    if(root == nullptr)
    {
        return;
    }
    _inorder(root->_left);
    cout << root->_key << " ";
    _inorder(root->_right);
}



